package com.clstu.tree;

/**
 * 演示 线索化二叉树的线索化过程 和遍历线索化二叉树
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        //测试
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        HeroNode1 node1 = new HeroNode1(1, "tom");
        HeroNode1 node2 = new HeroNode1(2, "jack");
        HeroNode1 node3 = new HeroNode1(3, "smith");
        HeroNode1 node4 = new HeroNode1(4, "mary");
        HeroNode1 node5 = new HeroNode1(5, "along");
        HeroNode1 node6 = new HeroNode1(6, "mac");
        HeroNode1 node7 = new HeroNode1(7, "alice");
        threadedBinaryTree.setRoot(node1);
        node1.setLeft(node2);
        node1.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        node3.setRight(node7);
        threadedBinaryTree.infixOrder();
//        //前序线索化(线索化之后就不能按照原先的遍历方式遍历了)
//        threadedBinaryTree.preThreadNodes();
//        //中序线索化(线索化之后就不能按照原先的遍历方式遍历了)
//        threadedBinaryTree.infixThreadedNodes();
//        //后序线索化(线索化之后就不能按照原先的遍历方式遍历了)
        threadedBinaryTree.postThreadNodes();
        //测试
        System.out.println("========");
        System.out.println("前驱"+node5.getLeft());
        System.out.println("后继:"+node5.getRight());
//        System.out.println("==========");
//        threadedBinaryTree.infixOrder();
        System.out.println("遍历线索化二叉树");
        //专门针对线索化二叉树的遍历方式
//        threadedBinaryTree.threadTreeList();
//        threadedBinaryTree.threadTreeList2();
//        threadedBinaryTree.postThreadList();//后续遍历线索二叉树暂时未实现(需要再节点中添加父节点才可以完成!!)

    }
}
/**
 * HeroNode1节点类
 */
class HeroNode1{
    private int id ;
    private String name;
    private HeroNode1 left;
    private HeroNode1 right;
    //定义左指针的类型,0表示左子树,1表示前驱节点
    private int leftType;
    //定义右指针的类型,0表示左子树,1表示后继节点
    private int rightType;

    //构造器
    public HeroNode1(int id,String name){
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode1 getLeft() {
        return left;
    }

    public void setLeft(HeroNode1 left) {
        this.left = left;
    }

    public HeroNode1 getRight() {
        return right;
    }

    public void setRight(HeroNode1 right) {
        this.right = right;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    //编写方法实现前序遍历,从自己开始
    public void preOrder(){
        //前序遍历:
        // 自己 ---> 左递归 ---> 右递归
        //自己
        System.out.println(toString());
        //左递归
        if(left!=null) {
            left.preOrder();
        }
        //右递归
        if(right!=null) {
            right.preOrder();
        }
    }

    //编写方法实现中序遍历
    public void infixOrder(){
        //中序遍历:
        // 左递归 ---> 自己 ----> 右递归
        //左递归
        if(left!=null){
            left.infixOrder();
        }
        //自己
        System.out.println(toString());
        //右递归
        if (right!=null){
            right.infixOrder();
        }
    }

    //编写方法实现后续遍历
    public void postOrder(){
        //后序遍历:
        // 左递归 ---> 右递归 ---> 自己
        //左递归
        if(left!=null){
            left.postOrder();
        }
        //右递归
        if(right!=null){
            right.postOrder();
        }
        //自己
        System.out.println(toString());
    }

    //编写方法实现前序遍历查找
    public HeroNode1 preFindById(int id){
        System.out.println("前序查找第"+(++BinaryTreeDemo.count1)+"次");
        //前序遍历
        //自己  ---> 左查找 ----> 右查找
        //自己
        if(this.id == id){
            return this;
        }
        HeroNode1 resNode;//用于返回
        //左查找
        if(left!=null){
            resNode = left.preFindById(id);
            if(resNode != null){
                return resNode;
            }
        }
        //右查找
        if(right!=null){
            resNode = right.preFindById(id);
            if(resNode!=null){
                return resNode;
            }
        }
        //没找到
        return null;
    }

    //编写方法实现中序遍历查找
    public HeroNode1 infixFindById(int id){
        System.out.println("中序查找第"+(++BinaryTreeDemo.count2)+"次");
        //中序遍历
        // 左查找 ---> 自己 -----> 右查找
        HeroNode1 resNode;
        //左查找
        if(left!=null){
            resNode = left.infixFindById(id);
            if(resNode != null){
                return resNode;
            }
        }
        //自己
        if(this.id == id){
            return this;
        }
        //右查找
        if(right!=null){
            resNode = right.infixFindById(id);
            if(resNode!=null){
                return resNode;
            }
        }
        //没找到
        return null;
    }

    //编写方法实现后序遍历查找
    public HeroNode1 postFindById(int id){
        System.out.println("后序查找第"+(++BinaryTreeDemo.count3)+"次");
        //后序遍历
        // 左查找 ----> 自己 ----> 右查找
        HeroNode1 resNode;
        //左查找
        if(left!=null){
            resNode = left.postFindById(id);
            if(resNode!=null){
                return resNode;
            }
        }
        //右查找
        if(right!=null){
            resNode = right.postFindById(id);
            if(resNode!=null){
                return resNode;
            }
        }
        //自己
        if(this.id == id){
            return this;
        }
        //没找到
        return null;
    }

    //编写方法实现二叉树的删除,成功返回true,失败返回false(简陋版本,如果找到直接置空,很有可能直接删掉子树)
    public boolean deleteById(int id){
        //思路分析:
        //因为数跟单链表一样,是单向的,不能自我删除,所以要在父节点上删除子节点
        //过程:
        //1.判断左节点,如果是,删除,返回true
        //2.判断右节点,如果是,删除,返回true
        //3.左递归删除
        //4.右递归删除
        //5.如果都没有找到,返回false
        //判断左节点
        if(left!=null) {
            if (left.getId() == id) {
                left = null;
                return true;
            }
        }
        //判断右节点
        if(right!=null) {
            if (right.getId() == id) {
                right = null;
                return true;
            }
        }
        //左递归
        if(left!=null){
            if(left.deleteById(id)){
                return true;
            }
        }
        //右递归
        if(right!=null){
            if(right.deleteById(id)){
                return true;
            }
        }
        //如果都没有删除成功
        return false;
    }

    //删除升级版,(如果被删除的节点右左子节点就用左子节点代替自己,否则右子节点代替自己)
    public boolean deleteById2(int id){
        //判断左边
        if(left!=null) {
            if (left.getId() == id) {
                //左子树代替
                if (left.getLeft() != null) {
                    left = left.getLeft();
                    return true;
                }
                //否则就是右子树代替
                left = left.getRight();
                return true;
            }
        }
        //判断右边
        if(right!=null) {
            if (right.getId() == id) {
                //左子树代替
                if (right.getLeft() != null) {
                    right = right.getRight();
                    return true;
                }
                //否则就是右子树代替
                right = right.getRight();
                return true;
            }
        }
        //左递归
        if(left!=null){
            if(left.deleteById2(id)){
                return true;
            }
        }
        //右递归
        if(right!=null){
            if(right.deleteById2(id)){
                return true;
            }
        }
        //如果都没有成功
        return false;
    }
}

/**
 * 线索化二叉树类(多了一个线索化的方法)
 */
class ThreadedBinaryTree{
    private static int count = 0;
    private HeroNode1 root ;
    //定义pre节点,在线索化的时候始终指向遍历节点的前驱节点,
    //原因:数是单向的无法直接找到前驱节点,只有多定义一个辅助变量,
    //注意:初始值null,线索化的第一个节点没有前驱节点,所以开始是null
    private HeroNode1 pre = null;

    public HeroNode1 getRoot() {
        return root;
    }

    public void setRoot(HeroNode1 root) {
        this.root = root;
    }

    //重载,中序线索化二叉树,底层仍然使用下面的方法,只是为了调用方便
    public void infixThreadedNodes(){
       infixThreadedNodes(root);
    }

    //重载,前序线索化二叉树,底层仍然使用下面的方法,只是为了调用方便
    public void preThreadNodes(){
        preThreadNodes(root);
    }

    //重载,后序线索化二叉树,底层仍然使用下面的方法,只是为了调用方便
    public void postThreadNodes(){
        postThreadNodes(root);
    }

    //编写方法线索化二叉树(中序线索化),参数node表示当前节点
    public void infixThreadedNodes(HeroNode1 node){
        System.out.println("前序线索化调用:"+(++count));
        //思路分析:
        //中序线索化(将二叉树中的悬空指针都指向它的中序遍历的前一个或后一个节点)
        //过程: 递归中序遍历二叉树,利用pre指针指向当前节点的前一个节点,
        // (将所有的null指针: left为空的,指向前驱, right为空的,指向后继 并使用leftType和rightType标记指针是子树类型还是前驱或后继)
        //如果不能线索化
        if(node == null){
            return;
        }
        //中序线索化 左线索化 ---> 自己 ----> 右线索化
        //左线索化
        infixThreadedNodes(node.getLeft());
        //线索化自己
        if(node.getLeft() ==null){
            //把左边改为前驱节点
            node.setLeft(pre);
            node.setLeftType(1);
        }
        //pre.right指向后继节点
        if(pre!=null ){//(线索化第一个节点pre为null)
            //不破坏原本的树结构的情况下
            if(pre.getRight() == null) {
                pre.setRight(node);
                pre.setRightType(1);
            }
        }
        //pre后移,保持pre始终指向node的前一个节点(下一轮递归),(很容易忘!!!!!)
        pre = node;
        //右线索化
        infixThreadedNodes(node.getRight());
    }

    //编写方法前序线索化二叉树
    public void preThreadNodes(HeroNode1 node){
        //思路,按照前序遍历的方式线索化,把null指针都指向前驱或后继(必须有pre帮助)
        //前序: 自己 ----> 左线索化 ------>右线索化
        //如果不能线索化
        if(node == null){
            return;
        }
        //自己
        if(node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if(pre!=null){
            //不破坏树的原本结构
            if (pre.getRight()==null){
                pre.setRight(node);
                pre.setRightType(1);
            }
        }
        //记录原先的pre(防止死循环的)
        HeroNode1 pre1 = pre;
        //pre后移
        pre = node;
        //左线索化(注意前面修改了left的值,加判断条件防止死循环)
        if(node.getLeft()!=pre1) {
            preThreadNodes(node.getLeft());
        }
        //右线索化
        preThreadNodes(node.getRight());

    }

    //编写方法后续线索化二叉树
    public void postThreadNodes(HeroNode1 node){
        //后序遍历,将node的空指针指向前驱或者后继(必须有pre帮助)
        //后续 : 左线索化 ----> 右线索化 -----> 自己
        //如果不能线索化
        if(node == null){
            return;
        }
        //左线索化
        postThreadNodes(node.getLeft());
        //右线索化
        postThreadNodes(node.getRight());
        //自己
        if(node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if(pre!=null){
            //不破坏树的原本结构
            if (pre.getRight()==null){
                pre.setRight(node);
                pre.setRightType(1);
            }
        }
        //pre后移
        pre = node;
    }

    //编写方法遍历线索化二叉树(非递归,中序)
    public void threadTreeList(){
        //思路分析:
        //先找到线索化二叉树的头节点,再用right指针指向下一个继续
        //遍历次序:先找到left,直到left是一个相对来说的头节点,打印(打印的是没有前驱节点的节点)
        //       循环判断右边,如果 rightType == 1,说明后继结点就是right,直接打印(打印的是有前驱节点的节点),右移
        //       如果rightType != 1了,右移,不打印,说明后继节点不一定是node了,又继续找left直到找到一个相对的头节点继续循环
        //       如果node == null ,说明遍历结束
        //如果链表空
        if(root==null){
            return;
        }
        //循环遍历
        HeroNode1 node = root;
        while (true){
            //如果遍历完
            if(node == null){
                break;
            }
            //左找相对头节点
            while (node.getLeftType() == 0){
                node = node.getLeft();
            }
            //打印
            System.out.println(node);//这个打印的是没有前驱节点的节点
            //循环判断右边
            while (node.getRightType() == 1){
                node = node.getRight();
                System.out.println(node);
            }
            //右移(后移)
            node = node.getRight();
        }
    }

    //编写方法遍历线索化二叉树(非递归,前序)
    public void threadTreeList2(){
        //思路分析:
        // 1.先打印自己,2.再先挨着向左遍历,遍历一个打印一个,
        // 3.如果左边走不下去了(node.left == null || node.leftType == 1) ,
        // 就node = node.right( 无论right的type是什么 ,都是这个顺序) .(循环123步,直到node == null退出)
        //如果链表空
        if(root==null){
            return;
        }
        //循环遍历
        HeroNode1 node = root;
        while (true){
            //如果遍历完
            if(node == null){
                break;
            }
            //打印
            System.out.println(node);//这个打印的是没有前驱节点的节点
            //左边
            while (node.getLeftType() == 0 && node.getLeft() != null){
                node = node.getLeft();
                System.out.println(node);
            }
            //右边
            node = node.getRight();
        }
    }

    //编写方法遍历线索化二叉树(非递归,后序)//代码较难,写不出!!!!
//    public void postThreadList(){
//        //思路分析:
//        // 1.先不断往左边找,直到找到没有左节点在判断是否可以打印(node.rightType == 1)
//        // 2.如果有右边的线索,就顺着线索打印,直到没有线索;
//        // 3.在执行 node = node.parent.right 右移
//        //重复上面3句话
//        //打印
//        //如果不用遍历
//        if(root == null){
//            return;
//        }
//        //遍历
//        HeroNode1 node = root;
//        HeroNode1 helper = root;//因为要逆着打印,线索不够用
//        while (true){
//            //如果遍历完
//            if(node == null){
//                break;
//            }
//            //找到最左节点
//            while (node.getRightType() == 0 && node.getLeft() != null){
//                node = node.getLeft();
//            }
//            //判断是否能打印
//            if(node.getRightType() == 1){
//                System.out.println(node);
//            }
//            //根据线索挨着打印
//            while (node.getRightType() == 1) {
//                node = node.getRight();
//                System.out.println(node);
//            }
//            //右移(必须要用到helper)
//            //找到父节点
//            while (helper.getLeft() != node){
//                System.out.println("帮助指针: "+helper);
//                helper = helper.getLeft();
//            }
//            //helper 和 node 同时右移
//            node = helper.getRight();
//            helper = node;
//        }
//        System.out.println(root);//因为root不能用循环遍历
//    }

    //编写方法前序遍历该二叉树
    public void preOrder(){
        //如果树为空
        if(root==null){
            System.out.println("当前二叉树为空");
            return;
        }
        root.preOrder();
    }

    //编写方法中序遍历
    public void infixOrder(){
        if(root==null){
            System.out.println("当前二叉树空");
            return;
        }
        root.infixOrder();
    }

    //编写方法后续遍历二叉树
    public void postOrder(){
        if(root==null){
            System.out.println("当前二叉树空");
            return;
        }
        root.postOrder();
    }

    //前序查找
    public HeroNode1 preFindById(int id){
        //先判断是否树空
        if(root==null){
            return null;
        }
        return root.preFindById(id);
    }

    //中序查找
    public HeroNode1 infixFindById(int id){
        //是否树空
        if(root==null){
            return null;
        }
        return root.infixFindById(id);
    }

    //后续查找
    public HeroNode1 postFindById(int id){
        //是否树空
        if(root == null){
            return null;
        }
        return root.postFindById(id);
    }

    //删除(删除子树版)
    public boolean deleteById(int id){
        //先判断是否链表空
        if(root==null){
            return false;
        }
        //如果要删除的就是根节点
        if(root.getId()==id){
            root = null;
            return true;
        }
        //递归删除
        return root.deleteById(id);
    }

    //删除,升级版,可以保留一边,不完全删除子树
    public boolean deleteById2(int id){
        //先判断是否数空
        if(root == null){
            return false;
        }
        //如果要删除的是根节点
        if(root.getId() == id){
            //左边代替
            if(root.getLeft()!= null){
                root = root.getLeft();
                return true;
            }
            //否则右边代替
            root = root.getRight();
            return true;
        }
        //递归删除
        return root.deleteById2(id);
    }
}